The invention relates to a method, a device and a system for verifying points determined on an elliptic curve.
Cryptographic techniques based on elliptic curves are very efficient; the particular reason for this is that unlike previously known cryptographic techniques, there are no known attack methods having a subexponential running time for these techniques. In other words, this means that the increase in security per bit of the security parameters used is greater for techniques based on elliptic curves, and hence significantly shorter key lengths can be used for practical applications.
Hence cryptographic techniques based on elliptic curves have a higher performance and require a smaller bandwidth to transmit the system parameters than other cryptographic techniques with a comparable level of achievable security.
The known Diffie-Hellman technique for shared-key agreement between two communications users based on elliptic curves shall be outlined here as an example. In this technique, the first communications user A knows a security parameter ra and the second communications user B knows a security parameter rb. Once the two communications users have agreed on an elliptic curve and on a shared point P on this elliptic curve, the communications user A determines a valueQa=ra*P and the communications user B determines a valueQb=rb*P. 
Then the communications user A sends the value Qa to the communications user B, and the communications user B sends the value Qb to the communications user A. In a further scalar multiplication, the communications user A now determines the shared keyK=ra*Qb=ra*rb*P and the communications user B determines the same shared keyK=rb*Qa=rb*ra*P. 
These scalar multiplications thus form a fundamental component of cryptographic techniques based on elliptic curves. The use of elliptic curves is particularly advantageous because the inverse operationra,b=Qa,b/P can only be calculated using a considerable amount of computing effort. Based on today's level of knowledge, the scalar multiplication can be computed in polynomial time, but can only be inverted in exponential time.
Known cryptographic techniques based on elliptic curves are prone to violation by “side-channel attacks”, however.
Side-channel attacks are a class of methods for cryptographic analysis. Unlike conventional attacks on cryptographic applications, in this case an attacker does not attempt to break the underlying abstract mathematical algorithm, but attacks a specific implementation of a cryptographic technique. To do this, the attacker uses easily accessible physical measured quantities of the specific implementation, such as the computation running time, the power consumption and the electromagnetic radiation of the processor during the computation, or the response of the implementation to induced errors. The physical measurements from a single computation can be analyzed directly, for example in a simple power analysis, SPA, or an attacker records the measurements from a plurality of computations using a storage oscilloscope, for example, and then performs a statistical analysis, for example in a differential power analysis, DPA. Side-channel attacks are often far more efficient than crypto-analytic techniques and may even break techniques that are considered secure in terms of the algorithm, if the implementation of these algorithms is not protected against side-channel attacks. Hence it has been recognized that the actual implementation of cryptographic techniques based on elliptic curves is critical to the degree of achievable security of the respective applications that is ultimately obtained. Such measures to counter side-channel attacks are essential for smart cards and embedded applications in particular.
“Error analysis” is an example of these side-channel attacks. In this technique, an attacker systematically manipulates the operating parameters of an implementation of a cryptographic technique to cause transient or permanent errors during the cryptographic computation. The attack is possible because the correct operation of a component, such as a smart card or an embedded system, can only be guaranteed by the manufacturer within preset environmental conditions. Hence there is a broad spectrum of technical opportunities for generating such errors, such as manipulating the clock generation, fluctuations in the supply voltage, over-temperature or under-temperature, flashes of light or selective interference using a laser, partial destruction of the electric circuits, high-level radiation etc. The differences between outputs from the circuit during correct and faulty operation can provide an attacker with information on secret data, for instance on secret keys, depending on the error model used in the implementation. With some cryptographic techniques, a single incorrect computational result is enough to result in the secret key being divulged immediately. Security-related implementations must therefore include suitable countermeasures to protect against error analysis.
Previously known countermeasures range from sensors that monitor the environmental conditions and prevent execution of the cryptographic computations in the event of inadmissible operating conditions, to algorithmic protective measures. Algorithmic protective measures, for example, can perform the cryptographic computation twice and compare the two results with each other. This has the disadvantage, however, of twice the computing effort and consequently at least double the computing time. In another known countermeasure to protect against error analyses, invariants are introduced in intermediate results of the cryptographic technique that must remain intact throughout the entire computation. Before the result of the computation is output, the device checks whether the invariant is still valid at the end of the computation. If an error occurred, it is extremely likely that the invariant is no longer satisfied. Once again, however, this method has the disadvantage that a plurality of additional computing steps need to be made and hence high demands are placed on the required computing capacity and available memory space.
In certain environments on which cryptographic techniques are to be implemented, such as smart cards or RFID chips, however, it is necessary to allow for specific requirements as regards available computing capacity and existing memory space. In these environments, however, the aforementioned techniques for defending against side-channel attacks, in particular against error analyses, have the disadvantage that they cannot be used in such systems because they require a large amount of computing capacity and available memory space.